The present invention relates generally to bitmap compression, and particularly to methods for managing and compressing bitmaps.
Currently, bitmap structures are widely used in various fields of computer science, such as Database Management Systems and File Systems among others. These bitmap structures, or bitmaps, require a considerable amount of space to store the bitmap. For example, in a File System, one bit is typically used to represent a disk block. Presently, general purpose disks can handle terabytes (TB) of space, which means a large bitmap is required to manage all space in each disk. In Database Management Systems, bitmaps are typically used to accelerate decision support queries, where each bit is mapped to a corresponding record. Thus, a bitmap is set if the corresponding record has a property (P). In many cases, the bitmap is stored in a secondary storage device to save space in principal memory (such as RAM, ROM, flash, etc.). Generally, there is a considerable delay because each time that a bit that is to be accessed is stored on disk, the block that contains that bit is read from the disk and then stored in memory. Using compression techniques, the bitmap can be stored completely in principal memory, such as RAM, thus reducing delays improving the performance of the system.
Methods for managing bitmaps for storage systems with large caches are particularly prone to these performance delays. A cache comprising inexpensive consumer flash of around 5% of the total disk storage can improve the system performance by a factor of about four. Such caches typically have a large bitmap to identify the disk blocks residing in the cache. The bitmap requires frequent updates as data is placed in and removed from the cache. Compressing such bitmaps may reduce the cost associated with the bitmap memory.